from typing import List


class Solution:
    def insert(self, pend, val):
        new = []
        for pos in range(len(pend)+1):
            _list = pend[:]
            _list.insert(pos, val)
            new.append(_list)
        return new

    def permute(self, nums: List[int]) -> List[List[int]]:
        start = [[nums[0]]]
        remind = nums[1:]
        p = 0
        while p < len(remind):
            temp_start = []
            for e in start:
                temp = self.insert(e, remind[p])
                temp_start += temp
            start = temp_start
            p+=1

        return start

if __name__ == '__main__':
    print("NOTICE: 用回溯法再做一遍；全排列: 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以按任意顺序返回答案。\n https://leetcode.cn/problems/permutations/\n")
    print("\n这次就仔细思考了，发现用逐个位置插入\n\n")
    test =[
            [10,1, 5, 7]
        ]
    for v in test:
        print('---', v)
        ret = Solution().permute(v)
        print(ret)